//class Solution {
//public:
//    vector<int> preorderTraversal(TreeNode* root) {
//        vector<int> ret;
//        if (root == nullptr) return ret;
//
//        stack<TreeNode*> st;
//        st.push(root);
//        while (st.size())
//        {
//            auto top = st.top();
//            ret.push_back(top->val);
//            st.pop();
//            if (top->right)
//                st.push(top->right);
//            if (top->left)
//                st.push(top->left);
//        }
//        return ret;
//    }
//};




class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ret;
        if (root == nullptr) return ret;

        stack<TreeNode*> st;
        TreeNode* cur = root;
        while (st.size() || cur)
        {
            while (cur)
            {
                st.push(cur);
                cur = cur->left;
            }

            auto top = st.top(); st.pop();
            ret.push_back(top->val);

            if (top->right)
                cur = top->right;
        }
        return ret;
    }
};